import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.lang.Integer;
/**
 * 
 * 电脑病毒感染
 * 
 * 题目描述

一个局域网内有很多台电脑，分别标注为 0 ~ N-1 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用 t 表示。

其中网络内一台电脑被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回-1。

给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间。

如图：path[i] = {i, j, t} 表示：电脑 i->j，电脑 i 上的病毒感染 j，需要时间 t。

输入描述
4
3
2 1 1
2 3 1
3 4 1
2
输出描述
2
用例
输入	4
3
2 1 1
2 3 1
3 4 1
2
输出	2
说明	
第一个参数：局域网内电脑个数N，1 ≤ N ≤ 200；
第二个参数：总共多少条网络连接
第三个 2 1 1 表示2->1时间为1
第六行：表示病毒最开始所在电脑号2

 */

 /**
  * 
  题目解析
用例图示如下



病毒源头是2，其中：

2->1需要时间1

2->3需要时间1，3->4需要时间1

因此最少需要时间2才能感染所有电脑。

本题考察的是单源最短路径求解，解析可以参考：【精选】LeetCode - 743 网络延迟时间_leetcode 网络延迟时间_伏城之外的博客-CSDN博客

另外，本题题目描述和用例不符。因为题目说：

一个局域网内有很多台电脑，分别标注为 0 ~ N-1 的数字。
但是题目用例，第一行给出N=4，但是第五行出现了电脑编号也是4的情况。

这影响到了下面代码中dist、visited数组长度的定义。当前代码实现以用例数据为准，即认为电脑编号是 1~N。

具体考试时需要随机应变。
  */
public class 电脑病毒感染 {
    
    public static void main(String[] args) {
        
        try{

            Scanner scanner = new Scanner(System.in);

            //电脑数量
            int pcCount = scanner.nextInt();
            //电脑之间连接的连路数
            int lines = scanner.nextInt();

            //记录起点到达下个点的路径
            HashMap<Integer, List<int[]>> grahMap = new HashMap<>();
            for(int i=0; i<lines; i++){
                //出发点
                int startPoint = scanner.nextInt();
                //目标点
                int targetPoint = scanner.nextInt();
                //耗时
                int useTime = scanner.nextInt();

                grahMap.putIfAbsent(startPoint, new ArrayList<int[]>());
                grahMap.get(startPoint).add(new int[]{targetPoint, useTime});
            }

            //起点
            int sourcePoint = scanner.nextInt();

            // visited[i]:记录节点i是否找到最短路
            //boolean[] visited = new boolean[pcCount + 1];
 
            // dist[i]:记录源点到节点i的最短路
            int[] dist = new int[pcCount + 1];
            // 初始时，假设源点不可达其他剩余点，即源点到达其他点的耗时无限大
            Arrays.fill(dist, Integer.MAX_VALUE);
            // 源点到自身的耗时为0
            dist[sourcePoint] = 0;

            //pq用于记录[节点编号，节点到源点的距离]，排序规则是，节点到源点的距离越短，优先级越高
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            //从源点src开始发起探索
            priorityQueue.add(new int[]{sourcePoint, dist[sourcePoint]});

            while(!priorityQueue.isEmpty()){

                //取出局部最优（最短）路径的终点编号 u
                int u = priorityQueue.poll()[0];
                // 如果节点编号u已经找到了最短路，说明当前u是重复入队的点，因此无需继续探索
                //if (visited[u]) continue;
                // 否则记录当前u找到了最短路
                //visited[u] = true;

                // 如果u有可达的其他点
                if (grahMap.containsKey(u)) {
                    for (int[] next : grahMap.get(u)) {
                        // v是可达的其他店
                        // w是u->v的耗时
                        int v = next[0], w = next[1];
    
                        // 那么如果从源点到u点的耗时是dist[u]，那么源点经过u点到v点的耗时就是dist[u] + w
                        int newDist = dist[u] + w;
                        // 而源点到v的耗时之前是dist[v]，因此如果newDist < dist[v]，则找到更少耗时的路径
                        if (dist[v] > newDist) {
                            // 更新源点到v的路径，即更新v点权重
                            dist[v] = newDist;
                            // 将v点加入优先队列中参与下一轮局部最优路径比较
                            priorityQueue.add(new int[]{v, dist[v]});
                        }
                    }
                }


            }

             // dist记录的是源点到达其他各点的最短耗时，我们取出其中最大的就是源点走完所有点的最短耗时
            int ans = 0;
            for (int i = 1; i <= pcCount; i++) {
                ans = Math.max(ans, dist[i]);
            }
 
            // 如果存在某个点无法到达，则源点到该点的耗时为Integer.MAX_VALUE
            System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);

        }catch(Exception e){

            e.printStackTrace();
        }
    }
}
